An Efficient Algorithm for Hamiltonian Path Embedding of $k$ -Ary $n$ -Cubes Under the Partitioned Edge Fault Model

一种在划分边故障模型下对 $k$ -元 $n$ -立方体进行哈密顿路径嵌入的高效算法

A well-designed fault-tolerant routing algorithm can address the fault tolerance challenges of NoCs by bypassing the faults when delivering packets. Routing algorithms should be not only fault-tolerant but also deadlock-free. The Hamiltonian path (H-path for short) strategy is a powerful tool for deadlock avoidance. Since the H-path traverses every node in the network exactly once and contains no cycle structure, the deadlock can be easily prevented by transmitting the packets along the H-path [7], [8], [9], [10], [11], [12], [13]. In recent years, this excellent strategy is utilized for designing fault-tolerant routing algorithms. For instance, the HamFA algorithm [7] is one of the most famous fault-tolerant routing algorithms using the H-path strategy. It constructs two directed subnetworks through the $\mathrm{H}$ -path strategy and limits packets to be routed in a single subnetwork so that the deadlock can be avoided. Simultaneously, HamFA can tolerate almost all one-faulty links. The FHOE algorithm [8] is also a fault-tolerant routing algorithm based on the H-path strategy for 2D NoCs. It fully combines the advantages of traditional odd-even turn model and HamFA strategy, and consequently can provide higher adaptivity and more choices of minimal paths compared to HamFA. Considering the importance of fault tolerance and extensive applications of the H-path in NoCs, it's natural to investigate the existence of the H-path in NoCs (i.e., the problem of embedding the H-path into NoCs), especially when faults occur (i.e., the fault-tolerant problem of embedding the H-path into NoCs). However, it is well-known that the problem of embedding an $\mathrm{H}$ -path into a network is NP-complete, even when no fault exists.

NoCs usually take interconnection networks as their underlying topology, which inherently affects the performance of NoCs. The $k$ -ary $n$ -cube $Q_n^k$ is one of the most important interconnection networks for building NoCs owing to its desirable properties, such as regularity, recursive structure, node symmetry, edge symmetry, low-latency, and ease of implementation [14]. The two associated parameters $k$ and $n$ in $Q_n^k$ provide it the ability to satisfy structural needs in a variety of circumstances. A commercial VLSI chip named the Tours Routing Chip (TRC) was designed early to perform wormhole routing in an arbitrary $k$ -ary $n$ -cube [15]. Furthermore,many fault-tolerant deadlock-free routing algorithms have been developed in $Q_n^k$ -based NoCs [16], [17],[18]. The desirable properties of $Q_n^k$ have even attracted a lot of research actually to build data center networks (DCNs), such as CamCube [19], NovaCube [20], CLOT [21], and Wave-Cube [22]. Though the scale of DCNs is much larger than that of NoCs, $k$ -ary $n$ -cubes can easily cope with it. It’s worth pointing out that stronger fault tolerance is necessary for the DCN since it possesses a lot of servers. Moreover, a lot of well-known parallel computing systems like iWarp [23], J-machine [24], Cray T3D [25], Cray T3E [26], and IBM Blue Gene/L [27] all have adopted $k$ -ary $n$ -cubes as their underlying topologies. These $Q_n^k$ - based architectures usually have high bisection width, high path diversity, high scalability, and affordable implementation cost.

In order to apply the attractive H-path structure in $Q_n^k$ with as many faults as possible, the fault-tolerant problem of embedding the H-path into $Q_n^k$ has been extensively investigated in [28], [29],[30],[31],[32],[33],[34]. A network $G$ is Hamiltonian-connected if an H-path exists between any two nodes in $G$ . Also, $G$ is $f$ -edge fault-tolerant Hamiltonian-connected provided it is Hamiltonian-connected after removing arbitrary $f$ edges in $G$ . Yang et al. [32] proved that for any odd integer $k\ge 3,Q_n^k$ is(2n - 3)-edge fault-tolerant Hamiltonian-connected. Stewart and Xiang [33] proved that for any even integer $k\ge 4$ ,there is an $\mathrm{H}$ -path between any two nodes in different partite sets in $Q_n^k$ with at most $2n-2$ faulty edges. Yang and Zhang [34] recently showed that for every odd integer $k,Q_n^k$ admits an $\mathrm{H}$ -path between any two nodes that avoids a set $F$ of faulty edges and passes through a set $L$ of prescribed linear forests when $\left|E\left(L\right)\right|+\left|F\right|\le 2n-3$ . All the above results are obtained under the traditional fault model, which doesn't exert any restriction on the distribution of faulty edges. However, Yuan et al. [35] and $\mathrm{Xu}$ et al. [36] respectively pointed out that this model has many flaws in the realistic situation since it ignores the fact that it's almost impossible for all faulty nodes (resp. faulty edges) to be adjacent to the same node simultaneously (unless that the node fails). In other words, the fault tolerance assessment approaches under the traditional fault model seriously underestimate the fault tolerance potential of $Q_n^k$ .

The conditional fault model was proposed for tolerating more faulty edges by restricting each node to be adjacent to at least two fault-free edges. Under this model, Wang et al. [29] proved that for any even integer $k\ge 4$ ,there is an $\mathrm{H}$ -path between any two nodes in different partite sets in $Q_n^k$ with at most $4n-5$ conditional faulty edges. Though the fault tolerance they obtained is about twice that under the traditional fault model, it remains linearly correlated with $n$ . In addition,all the literature mentioned above only provides theoretical proofs about the existence of the $\mathrm{H}$ -path in $Q_n^k$ ,while executable fault-tolerant $\mathrm{H}$ -path embedding algorithms and their performance analysis are missing. Thus, this may hinder the practical application of the $\mathrm{H}$ -path on $Q_n^k$ .

In this paper, we pay more attention to the distribution pattern of faulty edges in each dimension of $Q_n^k$ . This consideration is based on the fact that various dimensions of $Q_n^k$ usually possess different faulty features in practical fields. For example, to minimize the fabrication cost of TSV links, $Q_n^k$ -based 3D $\mathrm{NoCs}$ are often designed with only partial connection in the vertical dimension (i.e., partial TSVs) [37], [38]. Particularly, the TSV density of 3D NoCs was suggested for only 12.5% in [38]. It implies that only 12.5% of vertical links are available, and 87.5% of vertical links can be deemed faulty. In other words, many missed links exist in one dimension inherently when $Q_n^k$ is utilized for building 3D NoCs. In this case, we can deem the vertically partially connected NoC topology as a $Q_n^k$ with many faulty links concentrated at the same dimension.

Based on the above concerns, for a class of networks that exhibit different faulty features in each dimension, we introduce another fault model, named the partitioned edge fault model (PEF model for short), to help such networks achieve a better fault-tolerant capacity. In essence, this model imposes different restrictions on faulty edges in each dimension according to flawed features. In fact, these restrictions are similar to the concept recently proposed by Zhang et al. [39], which pointed out that restricting the number of faulty edges in each dimension is quite important for reflecting the actual fault-tolerant capacity of a network and can be utilized to improve network edge connectivity. Thus, we utilize the PEF model to explore the fault tolerance potential of $Q_n^k$ when embedding an H-path into $Q_n^k$ with $n\ge 2$ and odd $k\ge 3$ and evaluate the performance of our approach. Our contributions are presented as follows:

1) We propose a new fault model, the PEF model, to improve the fault tolerance of $Q_n^k$ when we embed an H-path into the faulty $Q_n^k$ .

2) Under the PEF model, we provide a theoretical analysis for proving the existence of the $\mathrm{H}$ -path in $Q_n^k-F$ ,where $F$ is a PEF set (defined in Section III) such that $\left|F\right|\le$ $\frac{k^n-k^2}{k-1}-2n+5$

3) Based on the obtained theoretical results, we design an $O\left(N\right)$ algorithm,named $HP-PEF$ ,for embedding the $\mathrm{H}$ - path into $Q_n^k$ under the PEF model,where $N$ is the number of nodes in $Q_n^k$ . To our knowledge,this is the first time that an algorithm is not only proposed and proved correct, but also actually implemented, for H-path embedding into an edge-faulty $Q_n^k$ .

The implementation of the algorithm afforded us the ability to observe some features of the generated $\mathrm{H}$ -paths. For example,if an edge connecting nodes $u$ and $v$ became faulty,then the path length of $u$ and $v$ in the generated $\mathrm{H}$ -path can be an indicator of how important the missed edge is. By experimenting with the algorithm, we gather the data of average path lengths for all edges in the generated $\mathrm{H}$ -path.

Our algorithm is shown to outperform all known similar works in terms of tolerated faulty-edges. In particular, compared to [32],the improvement is from linear(2n - 3) to exponential $\frac{k^n-k^2}{k-1}-2n+5$ . We also show that HP-PEF can support the dynamic degradation of average success rate of constructing required $\mathrm{H}$ -paths even when increasing faulty edges exceed $\frac{k^n-k^2}{k-1}-2n+5$ .

Organization: The rest of this paper is organized as follows. In Section II, we provide the preliminaries used throughout this paper. In Section III, we first present the definition of the PEF model, and then give the theoretical proof related to the existence of the H-path in $Q_n^k$ under the PEF model. In Section IV,we design the fault-tolerant H-path embedding algorithm HP-PEF based on the theoretical basis in Section III and offer a detailed example for illuminating the execution process of HP-PEF. In Section V, we evaluate the performance of our method by implementing computer programs. Section VI concludes this paper.

For terminologies and notations not defined in this subsection, please refer to the reference [40]. An interconnection network can be modeled as a graph $G=\left(V\left(G\right),E\left(G\right)\right)$ ,where $V\left(G\right)$ represents its node set and $E\left(G\right)$ represents its edge set. The notations $\left|V\left(G\right)\right|$ and $\left|E\left(G\right)\right|$ denote the size of $V\left(G\right)$ and $E\left(G\right)$ , respectively. Given a graph $S$ ,if $V\left(S\right)\subseteq V\left(G\right)$ and $E\left(S\right)\subseteq$ $E\left(G\right)$ ,then $S$ is a subgraph of $G$ . Given a node set $M\subseteq V\left(G\right)$ , the subgraph of $G$ induced by $M$ ,denoted by $G\left[M\right]$ ,is a graph with the node set $M$ and edge set $\{\left(u,v\right)\in E\left(G\right)\mid u,v\in M\}$ . Let $F$ be a faulty edge set of $G$ ,and $G-F$ be the graph with the node set $V\left(G\right)$ and the edge set $E\left(G\right)-F$ . Given a positive integer $n$ ,we denote the set $\{1,2,\dots ,n\}$ as $\left[n\right]$ . Moreover,let ${\mathbb{Z}}_n=\left[n-1\right]\cup \{0\}$ when $n\ge 2$ and ${\mathbb{Z}}_1=\{0\}$ . A graph $P=$ $\left(v_0,v_1,\dots ,v_p\right)$ is called a path if $p+1$ nodes $v_0,v_1,\dots ,v_p$ are distinct and $\left(v_i,v_{i+1}\right)$ is an edge of $P$ with $i\in {\mathbb{Z}}_p$ . The length of $P$ is the number of the edges in $P$ . If $V\left(P\right)=V\left(G\right)$ ,then $P$ is a Hamiltonian path (H-path for short) of $G$ .

Definition II.1. (See [33]). The $k$ -ary $n$ -cube $Q_n^k$ is a graph with the node set $V\left(Q_n^k\right)=\{0,1,\dots ,k-1{\}}^n$ such that two nodes $u=u_{n-1}{u}_{n-2}\cdots u_0$ and $v=v_{n-1}{v}_{n-2}\cdots v_0$ are adjacent in $Q_n^k$ if and only if there is an integer $i\in {\mathbb{Z}}_n$ satisfying $u_i=v_i\pm 1\left(\mathrm{mod}k\right)$ and $u_j=v_j$ for every $j\in {\mathbb{Z}}_n-\{i\}$ . In this case,such an edge(u,v)is called an $i$ -dimensional edge for $i\in {\mathbb{Z}}_n$ ,and the set of all $i$ -dimensional edges of $Q_n^k$ is denoted by $E_i\left(Q_n^k\right)$ ,or $E_i$ for short.

Hereafter,for brevity,we will omit "(mod $k$ )" in a situation similar to the above definition. By Definition II.1, $Q_n^k$ is $2n$ -regular and contains $k^n$ nodes. In addition, $Q_n^k$ is edge symmetric [41]. The $Q_n^k$ can be partitioned into $k$ disjoint subgraphs $Q_n^k\left[0\right],Q_n^k\left[1\right],\dots ,Q_n^k\left[k-1\right]$ (abbreviated as $Q\left[0\right],Q\left[1\right],\dots ,Q\left[k-1\right])$ along the $i$ -dimension for $i\in$ ${\mathbb{Z}}_n$ . All these $k$ subgraphs are isomorphic to $Q_{n-1}^k$ . Given a faulty edge set $F$ ,let $F_i\left[l,l+1\right]=\{\left(u,v\right)\mid u\in V\left(Q\left[l\right]\right),v\in$ $V\left(Q\left[l+1\right]\right)\text{and}\left(u,v\right)\in F\cap E_i\}$ . If there is no ambiguity, we abbreviate $F_i\left[l,l+1\right]$ to $F\left[l,l+1\right]$ . Each node of $Q\left[l\right]$ has the form $u=u_{n-1}{u}_{n-2}\cdots u_{i+1}l{u}_{i-1}\cdots u_0$ . The node $v=$ $u_{n-1}{u}_{n-2}\cdots u_{i+1}{l}^{\prime }{u}_{i-1}\cdots u_0$ is the neighbor of $u$ in $Q\left[l^{\prime }\right]$ if $l^{\prime }=l\pm 1$ ,which is denoted by $n^{l^{\prime }}\left(u\right)$ . To distinguish the positions of the subgraphs where different nodes are located, let $l_u=u_i=l$ . That is, $l_v=l_u\pm 1$ . Although the values of $l_u$ and $u_i$ are equal,the notation $l_u$ mainly focuses on the position $l$ rather than the dimension $i$ of node $u$ . Let $Q_n^k\left[\ell ,h\right]$ (abbreviated as $Q\left[\ell ,h\right]$ ) be the subgraph induced by node set $\{u\mid u\in$ $V\left(Q\left[j\right]\right)$ with $j=\ell ,\ell +1,\dots ,h-1,h\}$ . Moreover,we have $Q\left[\ell ,h\right]=Q\left[\ell \right]$ when $\ell =h$ ,and taken modulo $k$ ,we have $Q\left[\ell ,h\right]=Q_n^k$ when $h=\ell -1$ . A path in $Q\left[\ell ,h\right]$ is denoted by $P_{\ell ,h}$ with $V\left(P_{\ell ,h}\right)\subseteq V\left(Q\left[\ell ,h\right]\right)$ . For convenience,we abbreviate $P_{\ell ,h}$ to $P_{\ell }$ when $\ell =h$ ,and to $P$ when $h=\ell -1$ by taking modulo $k$ .

Fig. 1 shows $Q_1^3,Q_2^3$ ,and $Q_3^3$ . We color each edge according to its dimension. In Fig. 1(c),we partition $Q_3^3$ into 3 disjoint subgraphs $Q\left[0\right],Q\left[1\right]$ ,and $Q\left[2\right]$ along the 2-dimension. The subgraph $Q\left[0,1\right]$ is induced by node set $\{u\mid u\in V\left(Q\left[0\right]\right)\cup$ $V\left(Q\left[1\right]\right)\}$ . The node $u=110\in V\left(Q\left[1\right]\right)$ is adjacent to two nodes $v=010\in V\left(Q\left[0\right]\right)$ and $w=210\in V\left(Q\left[2\right]\right)$ . In addition, $v=n^0\left(u\right)$ and $w=n^2\left(u\right)$ . It’s easy to see that $l_v=$ $l_u-1=0$ and $l_w=l_u+1=2$ .

In particular,the $Q_2^k$ can be deemed a $k\times k$ grid with wraparound edges,where a node $u_{i,j}=ij$ is indexed by its row $i$ and column $j$ . Let $p,q\in {\mathbb{Z}}_k$ be two row indices with $p\ne q$ . If $p<q$ ,we define the row torus $rt\left(p,q\right)$ to be the subgraph of $Q_2^k$ induced by the nodes on rows $p,p+1,\dots ,q$ ,and particularly, all column edges between nodes on row $p$ and row $q$ are removed when $p=0$ and $q=k-1$ . Otherwise,if $p>q$ ,we define the row torus $rt\left(p,q\right)$ to be the subgraph of $Q_2^k$ induced by the nodes on rows $p,p+1,\dots ,k-1,0,\dots ,q$ ,and particularly,all column edges between nodes on row $p$ and row $q$ are removed when $p=q+1$ . Fig. 2 depicts the $rt\left(0,4\right)$ ,which is obtained by removing the column edges between nodes on row 0 and row 4 from $Q_2^5$ . Throughout,we assume that the addition of row or column indices is modulo $k$ .

Fig. 1. The structures of (a) $Q_1^3$ ; (b) $Q_2^3$ ; (c) $Q_3^3$ .

Fig. 2. The structure of $rt\left(0,4\right)$ .

For the row torus $rt\left(p,q\right)$ with $q-p=1$ ,we define the four types of paths in $rt\left(p,q\right)$ as follows. The notations of these paths are derived from the shape of their pictorial representations, where $\overline{i}=q+p-i$ .